
import java.util.*;



public class Main {

//    public static double findMaxAverage(int[] nums, int k) {
//        int left = 0,right = 0, len = nums.length;
//        double sum = 0;
//        double ret = Double.MIN_VALUE;
//        while(right < len){
//            sum += nums[right];
//            if(right - left + 1 > k){
//                sum -= nums[left];
//                left++;
//            }
//            if(right - left + 1 == k){
//                double max = sum/k;
//                if(ret < max){
//                    ret = max;
//                }
//            }
//            right++;
//        }
//        return ret;
//    }
//
    private static ArrayList<ArrayList<Integer>> lists;
    private static ArrayList<Integer> list;
    public static ArrayList<ArrayList<Integer>> pathSum (TreeNode root, int sum) {
        lists = new ArrayList<>();list = new ArrayList<>();
        dfs(root, sum);
        return lists;
    }

    public static void dfs(TreeNode root, int sum){
        if(root == null && sum == 0){
            lists.add(new ArrayList<>(list));
            return;
        }
        if(root == null){
            return;
        }
        list.add(root.val);
        dfs(root.left, sum - root.val);
        list.remove(list.size() - 1);
        dfs(root.right, sum - root.val);
    }

    public static void main(String[] args) {
//        int[] arr = {-1};
//        findMaxAverage(arr,1);
//        TreeNode treeNode = null;
        pathSum(null,1);
        System.out.println(lists);
    }
//
//    public static String solve (String s, String t) {
//        int lens = s.length(), lent = t.length();
//        StringBuffer str = new StringBuffer();
//        int num = 0;
//        while(lens != 0 && lent != 0){
//            num += (s.charAt(lens - 1) - '0') + (t.charAt(lent - 1) - '0');
//            str.append(num%10);
//            num /= 10;
//            lens--;
//            lent--;
//        }
//        while(lens != 0){
//            num += s.charAt(lens - 1) - '0';
//            str.append(num % 10);
//            num /= 10;
//            lens--;
//        }
//        while(lent != 0){
//            num += t.charAt(lent - 1) - '0';
//            str.append(num % 10);
//            num /= 10;
//            lent--;
//        }
//        if(num != 0){
//            str.append(num);
//        }
//        return str.reverse().toString();
//    }
//
//    public static void main33(String[] args) {
//        System.out.println(solve("1011111111111111111111", "99"));
////        int[] arr = {6,8,10,0,2,4};
////        search(arr,10);
////        Map<Integer,Integer> map = new HashMap<>();
////        map.containsKey()
//        //
//        List<Integer> list1 = new ArrayList<>();
//        //int[] arr = list1.toArray();
//        Queue<Integer> queue = new LinkedList<>();
//        queue.poll();
//        String s;
//        List<Integer> list2 = new ArrayList<>(list1);
//
//    }
//
//    public static int search (int[] nums, int target) {
//        for(int i = 0; i < nums.length; i++){
//            if((nums[i] == target && (i - 1 >= 0 && i + 1 < nums.length)) && (nums[i - 1] < nums[i] && nums[i] > nums[i + 1])){
//                return i;
//            }
//            if(nums[i] == target && (i - 1 < 0 || i + 1 >= nums.length)){
//                return i;
//            }//
//        }
//        return -1;
//    }
//
//    public static String minWindow(String S, String T){
//        Queue<Character> queue = new LinkedList<>();
//        int[] Tc = new int[26];
//        int[] Sc = new int[26];
//        for(int i = 0; i < T.length(); i++){
//            Tc[T.charAt(i) - 'A']++;
//        }
//        int min = S.length();
//        String ret = null;
//        for(int i = 0; i < S.length(); i++){
//            char c = S.charAt(i);
//            queue.add(c);
//            while (!queue.isEmpty() && Tc[queue.peek() - 'A'] == 0){
//                queue.poll();
//            }
//            if(minWindow(Sc, Tc)){
//                if(min > queue.size()){
//                    ret = getMin(queue);
//                    min = queue.size();
//                }
//            }
//            if(Sc[c - 'A'] > Tc[c - 'A'] && queue.peek() == c){
//                queue.poll();
//                continue;
//            }
//            if(Tc[c - 'A'] != 0){
//                Sc[c - 'A']++;
//            }
//        }
//        if(minWindow(Sc, Tc)){
//            if(min >= queue.size()){
//                ret = getMin(queue);
//                min = queue.size();
//            }
//        }
//        if(ret == null){
//            return "";
//        }
//        return ret;
//    }
//
//    private static String getMin(Queue<Character> queue) {
//        int size = queue.size();
//        StringBuilder str = new StringBuilder();
//        while (size != 0){
//            char c = queue.poll();
//            str.append(c);
//            queue.add(c);
//            size--;
//        }
//        return str.toString();
//    }
//
//    private static boolean minWindow(int[] sc, int[] tc) {
//        for(int i = 0; i < 26; i++){
//            if(sc[i] < tc[i]){
//                return false;
//            }
//        }
//        return true;
//    }
//
//    public static void main31(String[] args) {
//        String s = "ADOBECODEBANC";
//        String t = "ABC";
//        String ret = minWindow(s, t);
////        PriorityQueue queue = new PriorityQueue<>(()->{
////            return 1 - 2;
////        });
//
//        System.out.println(ret);
//    }
//    public static void duplicateZeros(int[] arr) {
//        int i = 0,j = 0,len = arr.length;
//        while(j < len){
//            if(arr[i] == 0){
//                j++;
//            }
//            if(j >= len - 1){
//                break;
//            }
//            i++;
//            j++;
//        }
//        if(arr[i] == 0 && j == len){
//            arr[j - 1] = 0;
//            i--;
//            j -= 2;
//        }
//        while(i > 0){
//            if(arr[i] == 0){
//                arr[j--] = 0;
//                arr[j--] = 0;
//            }else{
//                arr[j--] = arr[i];
//            }
//            i--;
//        }
//    }
//
//    public static int[] MySort (int[] arr) {
//        // write code here
//        if(arr == null || arr.length <= 1){return arr;}
//        quickSort(arr, 0, arr.length - 1);
//        return arr;
//    }
//
//    private static void quickSort(int[] arr, int l, int r){
//        if(l >= r){return;}
//        int left = l;
//        int right = r;
//        int midNum = arr[l];
//        while(left < right){
//            while(left < right && arr[right] >= midNum){right--;}
//            if(left < right){arr[left] = arr[right];}
//            while(left < right && arr[left] < midNum){left++;}
//            if(left < right){arr[right] = arr[left];}
//        }
//        arr[left] = midNum;
//        quickSort(arr, l, left - 1);
//        quickSort(arr, left + 1, r);
//    }

//    public static void main30(String[] args) {
////        String s = "A man, a plan, a canal: Panama";
////        //isPalindrome(s);
////        List<ArrayList<Integer>> lists = new ArrayList<>();
////        System.out.println(lists);
//
//        int[] arr = {5,2,3,1,4};
//        MySort(arr);
//        System.out.println(Arrays.toString(arr));
//
//    }
//
//    public static int InversePairs (int[] nums) {
//        int amount = 0;
//        for(int i = 0; i < nums.length - 1; i++){
//            int p = nums[i];
//            for(int j = i + 1; i < nums.length; j++){
//                if(p > nums[j]){
//                    amount++;
//                }
//            }
//        }
//        return amount % 1000000007;
//    }
//
//    public static boolean isPalindrome(String s) {
//        int left = 0;
//        int right = s.length() - 1;
//        while(left < right){
//            while((s.charAt(left) < 'a' && s.charAt(left) > 'z')||(s.charAt(left) < 'A' && s.charAt(left) > 'Z')){
//                left++;
//            }
//            while((s.charAt(right) < 'a' && s.charAt(right) > 'z')||(s.charAt(right) < 'A' && s.charAt(right) > 'Z')){
//                right--;
//            }
//            if(s.charAt(left) != s.charAt(right) ||
//                    (char)(s.charAt(left) - 32) != s.charAt(right) ||
//                    (char)(s.charAt(left) + 32) != s.charAt(right)){
//                return false;
//            }
//            left++;
//            right--;
//        }
//        return true;
//    }
//
//    public static String[] strs = {" ", " ", "abc",
//            "def", "ghi", "jkl",
//            "mno", "pqrs", "tuv", "wxyz"};
////    public static StringBuilder s = new StringBuilder();
////    public static List<String> list = new ArrayList<>();
//
//    public static void dfs(int index, String digits, int len){
//        if(index == len){
//            //list.add(s.toString());
//            return;
//        }
//        int s1 = digits.charAt(index) - '0';
//        for(int i = 0; i < strs[s1].length(); i++){
//            s.append(strs[s1].charAt(i));
//            dfs(index + 1, digits, len);
//            s.deleteCharAt(index);
//        }
//    }
//
//    public static List<String> letterCombinations(String digits) {
//        if(digits == null || digits.length() == 0){
//            return new ArrayList<String>();
//        }
//        dfs(0, digits, digits.length());
//        return list;
//    }
//
//    public static void main25(String[] args) {
//        letterCombinations("2");
//        System.out.println(list.toString());
//        int[] arr = {1,2,3,4};
//        String s = "aa//d//dc";
//        String[] str = s.split("/");
//        char c = 'a';
//
//    }
//
//    public static int myAtoi(String s) {
//        char f = '+';
//        char[] cs = s.toCharArray();
//        int i = 0;
//        for(i = 0; i < cs.length; i++){
//            if(cs[i] == ' '){
//                continue;
//            }
//            if(cs[i] == '+' || cs[i] == '-'){
//                f = cs[i];
//                break;
//            }
//            return 0;
//        }
//        i++;
//        while(i < cs.length){
//            if(cs[i] != '0'){
//                break;
//            }
//            i++;
//        }
//        if(i == cs.length){
//            return 0;
//        }
//        long sum =(long) (cs[i] - '0');
//        for(; i < cs.length; i++){
//            if(cs[i] == ' ') continue;
//            if(cs[i] <= '0' && cs[i] >= '9') break;
//            sum = (long)(sum * 10 + cs[i] - '0');
//            if(f == '-' && sum >= (Integer.MAX_VALUE + 1)){
//                return Integer.MIN_VALUE;
//            }
//            if(f == '+' && sum >= Integer.MAX_VALUE){
//                return Integer.MAX_VALUE;
//            }
//        }
//        return (int) sum;
//    }
//
//    public static String convert(String s, int numRows) {
//        if(numRows < 2) return s;
//        List<StringBuilder> rows = new ArrayList<StringBuilder>();
//        for(int i = 0; i < numRows; i++) rows.add(new StringBuilder());
//        int i = 0, flag = -1;
//        for(char c : s.toCharArray()) {
//            rows.get(i).append(c);
//            if(i == 0 || i == numRows -1) flag = - flag;
//            i += flag;
//        }
//        StringBuilder res = new StringBuilder();
//        for(StringBuilder row : rows) res.append(row);
//        return res.toString();
//    }
//
//    public static String convert1(String s, int numRows) {
//        if(s.length() <= 2 || numRows == 1){
//            return s;
//        }
//        List<StringBuilder> list = new ArrayList<>();
//        for(int i = 0; i < numRows; i++) list.add(new StringBuilder());
//        int i = 0, flag = -1;
//        char[] chs = s.toCharArray();
//        for(char c : chs){
//            list.get(i).append(c);
//            if(i == 0|| i == numRows - 1){
//                flag = -flag;
//            }
//            i += flag;
//        }
//        StringBuilder str = new StringBuilder();
//        for(int j = 0; j < numRows; j++){
//            str.append(list.get(j));
//        }
//        return str.toString();
//    }
//
//    public static void main29(String[] args) {
//        Scanner in = new Scanner(System.in);
//        char[] s = in.next().toCharArray();
//        int x = 1;
//        int sum = 0;
//        for(int i = 0; i < s.length - 1; i++){
//            if(s[i] == '-'){
//                continue;
//            }
//            sum += x * (s[i] - '0');
//            x++;
//        }
//        char c = '0';
//        if(sum % 11 == 10){
//            c = 'X';
//        }else{
//            sum %= 11;
//            c = (char)(sum + '0');
//        }
//        if(c == s[s.length - 1]){
//            System.out.println("Right");
//        }else{
//            s[s.length - 1] = c;
//            String str = new String(s);
//            System.out.println(str);
//        }
//    }
//
//    public static void main28(String[] args) {
//        Scanner in = new Scanner(System.in);
//        // 注意 hasNext 和 hasNextLine 的区别
//        char[] chs = in.next().toCharArray();
//        int left = 0;
//        int right = 0;
//        int[] arr = new int[26];
//        int count = 0;
//        int max = 0;
//        while(right < chs.length){
//            char c = chs[right];
//            if(arr[c - 'a'] == 0){
//                count++;
//                arr[c - 'a']++;
//            }
//            while(count > 2){
//                char ch = chs[left];
//                arr[ch - 'a']--;
//                if(arr[ch - 'a'] == 0){
//                    count--;
//                }
//                left++;
//            }
//            if(right - left + 1 > max){
//                max = right - left + 1;
//            }
//            right++;
//        }
//        System.out.println(max);
//    }
//
//    public static void main27(String[] args) {
//        Scanner in = new Scanner(System.in);
//        // 注意 hasNext 和 hasNextLine 的区别
//        int n = in.nextInt();
//        int[][] arr = new int[n][n];
//        for(int i = 0; i < n; i++){
//            for(int j = 0; j < n; j++){
//                arr[i][j] = in.nextInt();
//            }
//        }
//        int q = in.nextInt();
//        while(q != 0){
//            int x = in.nextInt();
//            reverse(arr, x, n);
//            q--;
//        }
//        for(int i = 0; i < n; i++){
//            for(int j = 0; j < n; j++){
//
//                System.out.print(arr[i][j]);
//                System.out.print(" ");
//            }
//            System.out.println();
//        }
//    }
//    private static void reverse(int[][] arr, int x, int len){
//        if(x == 1){
//            int down = len - 1;
//            int up = 0;
//            while(down > up){
//                for(int i = 0; i < len; i++){
//                    int tmp = arr[up][i];
//                    arr[up][i] = arr[down][i];
//                    arr[down][i] = tmp;
//                }
//                down--;
//                up++;
//            }
//            for(int i = 0; i < len; i++){
//                int left = 0;
//                int right = len - 1;
//                while(left < right){
//                    int tmp = arr[i][left];
//                    arr[i][left] = arr[i][right];
//                    arr[i][right] = tmp;
//                    left++;
//                    right--;
//                }
//            }
//        }else{
//            int down = len - 1;
//            int up = 0;
//            while(down > up){
//                for(int i = 0; i < len; i++){
//                    int tmp = arr[up][i];
//                    arr[up][i] = arr[down][i];
//                    arr[down][i] = tmp;
//                }
//                down--;
//                up++;
//            }
//        }
//    }
//
//    public static void main26(String[] args) {
//        Scanner in = new Scanner(System.in);
//        int n = in.nextInt();
//        int[] arr = new int[n];
//        for(int i = 0; i < n; i++){
//            arr[i] = in.nextInt();
//        }
//        int q = in.nextInt();
//        int max = arr[0];
//        int[] dp = new int[n + 1];
//        for(int i = 2; i <= n; i++){
//            if(i == 2){
//                if(arr[i - 1] <= dp[i - 1]){
//                    dp[i] = arr[i - 1];
//                }else{
//                    dp[i] = max;
//                    max = arr[i - 1];
//                }
//            }else{
//                if(arr[i - 1] <= dp[i - 1]){
//                    dp[i] = dp[i - 1];
//                }else if(arr[i - 1] > dp[i - 1] && arr[i - 1] <= max){
//                    dp[i] = arr[i - 1];
//                }else{
//                    dp[i] = max;
//                    max = arr[i - 1];
//                }
//            }
//
//        }
//        while(q > 0){
//            int x = in.nextInt();
//            System.out.println(dp[x]);
//            q--;
//        }
//    }
//
////    private void add(int a, int b){
////        return;
////    }
////    private int add(int a, int b){
////        return a + b;
////    }
//
////    private int add(){
////
////    }
////    public static void main(String[] args) {
////        Map<String, Integer> map = new HashMap<>();
////        Integer result = map.get("sda");
////        System.out.println(result);
////        map.getOrDefault();
////        PriorityQueue
////    }
//
//    public static void main23(String[] args) {
//        Scanner in = new Scanner(System.in);
//        int q = in.nextInt();
//        while(q != 0){
//            char[] chs = in.nextLine().toCharArray();
//            int len = chs.length;
//            if(len == 1 && (chs[0] - '0') % 2 != 0){
//                System.out.println(-1);
//            }else{
//                if((chs[len - 1] - '0') % 2 == 0){
//                    System.out.println(new String(chs));
//                }else{
//                    int i = 0;
//                    for(i = 0; i < len - 1; i++){
//                        if((chs[i] - '0') % 2 == 0){
//                            char tmp = chs[i];
//                            chs[i] = chs[len - 1];
//                            chs[len - 1] = tmp;
//                            System.out.println(new String(chs));
//                            break;
//                        }
//                    }
//                    if(i == len - 1){
//                        System.out.println(-1);
//                    }
//                }
//            }
//            q--;
//        }
//    }
//
//    public static void main21(String[] args) {
//        Scanner in = new Scanner(System.in);
//        char[] chs = in.next().toCharArray();
//        int[] arr = new int[26];
//        for(int i = 0; i < chs.length; i++){
//            arr[chs[i] - 'a']++;
//        }
//        int max = 0;
//        int min = 100;
//        for(int i = 0; i < 26; i++){
//            if(arr[i] > max){
//                max = arr[i];
//            }
//            if(arr[i] < min && arr[i] != 0){
//                min = arr[i];
//            }
//        }
//        int abs = max - min;
//        if(abs == 0){
//            System.out.println("No Answer");
//            System.out.println(0);
//            return;
//        }
//        for(int i = 2; i < abs/2; i++){
//            if(abs % i == 0){
//                System.out.println("No Answer");
//                System.out.println(0);
//                return;
//            }
//        }
//    }
//
//    public static boolean hostschedule (int[][] schedule) {
//        int n = schedule.length;
//        int[] arr = new int[2 * n + 1];
//        int j = 1;
//        for(int i = 0; i < n; i++){
//            if(schedule[i][0] < arr[j - 1]){
//                return false;
//            }else{
//                arr[j] = schedule[i][0];
//                j++;
//            }
//            if(schedule[i][1] < arr[j - 1]){
//                return false;
//            }else{
//                arr[j] = schedule[i][1];
//                j++;
//            }
//        }
//        return true;
//    }
//
//    public static void main20(String[] args) {
//        int[][] arr = {{0,10}, {10, 20}, {20,30}};
//        boolean flag = hostschedule(arr);
//        System.out.println(flag);
//    }
//    public static void main18(String[] args) {
//        Scanner in = new Scanner(System.in);
//        int n = in.nextInt();
//        int[][] arr = new int[n][27];
//        for(int i = 0; i < n; i++){
//            char[] ch = in.nextLine().toCharArray();
//            for(int j = 0; j < ch.length; j++){
//                arr[i][ch[j] - 'a']++;
//            }
//        }
//        int sum = 0;
//        for(int i = 0; i < n; i++){
//            if(arr[i][26] == 1){
//                continue;
//            }else{
//                sum++;
//                String str1 = Arrays.toString(arr[i]);
//                for(int j = i + 1; j < n; j++){
//                    if(arr[j][26] == 1){
//                        continue;
//                    }else{
//                        String str2 = Arrays.toString(arr[j]);
//                        if(str1.equals(str2)){
//                            arr[j][26] = 1;
//                        }
//                    }
//                }
//            }
//        }
//        System.out.println(sum);
//    }
//    public static void main17(String[] args) {
//        Scanner in = new Scanner(System.in);
//        int a = in.nextInt();
//        int h = in.nextInt();
//        int b = in.nextInt();
//        int k = in.nextInt();
//        long sum = 0;
//        while(h > 0 && k > 0){
//            sum = a + b;
//            h -= b;
//            k -= a;
//        }
//        if(h > 0){
//            sum += a*10;
//        }else{
//            sum += b*10;
//        }
//        System.out.println(sum);
//    }
//
//    public static void main16(String[] args) {
//        Scanner in = new Scanner(System.in);//
//        // 注意 hasNext 和 hasNextLine 的区别
//        int day = in.nextInt();
//        int k = in.nextInt();
//        int[] ai = new int[day];
//        int[] bi = new int[day];
//        for(int i = 0; i < day; i++){
//            ai[i] = in.nextInt();
//        }
//        for(int i = 0; i < day; i++){
//            bi[i] = in.nextInt();
//        }
//        int n = day - k + 1;
//        long[] a = new long[n];
//        long[] b = new long[n];
//        long max = 0;
//        int x = 0;
//        int j = 0;
//        long suma = 0;
//        long sumb = 0;
//        for(int i = 0; i < n;){
//            if(j - i + 1 < k){
//                suma += ai[j];
//                sumb += bi[j];
//                j++;
//            }else{
//                suma += ai[j];
//                sumb += bi[j];
//                a[i] = suma;
//                b[i] = sumb;
//                suma -= ai[i];
//                sumb -= bi[i];
//                i++;
//                j++;
//                // if(j >= day){
//                //     break;
//                // }
//            }
//        }
//
//        for(int i = 0; i < n; i++){
//            if(a[i] > max){
//                max = a[i];
//                x = i;
//            }else if(a[i] == max && b[i] < b[x]){
//                x = i;
//            }else{
//                ;
//            }
//        }
//        System.out.println(x);
//
//    }
//
//    public static void main15(String[] args) {
//        Scanner in = new Scanner(System.in);
//        int n = in.nextInt();
//        int m = in.nextInt();
//        int[][] arr = new int[n + 2][m + 2];
//        for(int i = 1; i <= n; i++){
//            for(int j = 1; j <= m; j++){
//                arr[i][j] = in.nextInt();
//            }
//        }
//        for(int i = 1; i <= n; i++){
//            for(int j = 1; j <= m; j++){
//                long sum = arr[i][j] + arr[i - 1][j] + arr[i + 1][j] + arr[i][j - 1] + arr[i][j + 1];
//                System.out.print(sum + ' ');
//            }
//            System.out.println();
//        }
//    }
//
//    public static void main14(String[] args) {
//        Scanner in = new Scanner(System.in);
//        int n = in.nextInt();
//        StringBuilder str = getString(n);
//        if(str.length() == 0 || str.charAt(0) == '0'){
//            System.out.println(0);
//        }else{
//            String str1 = str.toString();
//            int m = Integer.parseInt(str1);
//            System.out.println(Integer.getInteger(str.toString()));
//        }
//    }
//    private static StringBuilder getString(int n){
//        StringBuilder str = new StringBuilder();
//        while(n != 0){
//            int m = n % 10;
//            if(m % 2 == 0){
//                str.append(0);
//            }else{
//                str.append(1);
//            }
//            n /= 10;
//        }
//        return str.reverse();
//    }
//
//    public static int minSubArrayLen(int target, int[] nums) {
//        int start = 0;
//        int end = 0;
//        int sum = 0;
//        int min = Integer.MAX_VALUE;
//        while(end < nums.length || sum > target){
//            if(sum < target){
//                sum += nums[end];
//                end++;
//
//            }else{
//                sum -= nums[start];
//                start++;
//                if(sum >= target){
//                    min = Math.min(end - start, min);
//                }
//            }
//        }
//        return min;
//    }
//
//    public static void main13(String[] args) {
//        int target = 7;
//        int[] arr = {2,3,1,2,4,3};
//        int min = minSubArrayLen(target, arr);
//        System.out.println(min);
//    }
//
//    public static void main12(String[] args) {
//        Scanner in = new Scanner(System.in);
//        int len = in.nextInt();
//        // 注意 hasNext 和 hasNextLine 的区别
//        int[] ch = new int[26];
//        String s = in.nextLine();
//        String str = in.nextLine();
//        for(int i = 0; i < len; i++){
//            ch[str.charAt(i) - 'a']++;
//        }
//        int max = 0;
//        StringBuilder strBuilder = new StringBuilder();
//        while(len != 0){
//            for(int i = 0; i < 26; i++){
//                if(ch[i] == 0){
//                    continue;
//                }
//                if(ch[i] > max){
//                    max = ch[i];
//                }
//                len--;
//                char c = (char)('a' + i);
//                strBuilder.append(ch);
//                ch[i]--;
//            }
//        }
//        if(max > len / 2){
//            System.out.println("no");
//        }else{
//            System.out.println(strBuilder.toString());
//        }
//
//    }
//
//    public static void main11(String[] args) {
//        Arrays.sort(new int[2]);
//        Map<String, String> map = new HashMap<>();
//        Scanner in = new Scanner(System.in);
//        // 注意 hasNext 和 hasNextLine 的区别
//        int n = in.nextInt();
//        String str = in.nextLine();
//        int[] chs = new int[26];
//        for(int i = 0; i < n; i++){
//            int x = str.charAt(i) - 'a';
//            chs[x]++;
//        }
//        int s = chs['s' - 'a'];
//        int h = chs['h' - 'a'];
//        int y = chs['y' - 'a'];
//        System.out.print(s * h * y);
//    }
//
//    public static int getLongestPalindrome (String A) {
//        int left = 0;
//        int right = A.length() - 1;
//        int retLeft = left;
//        int retRight = right;
//        int max = 1;
//        while(left != right){
//            retLeft = left;
//            retRight = right;
//            while(check(A, retLeft, retRight)){
//                retRight--;
//            }
//            if(retRight - retLeft + 1 > max){
//                max = retRight - retLeft + 1;
//            }
//            left++;
//        }
//        return max;
//    }
//    private static boolean check(String A, int left, int right){
//        while(left < right){
//            if(A.charAt(left) != A.charAt(right)){
//                return false;
//            }
//            left++;
//            right--;
//        }
//        return true;
//    }
//
//    public static void main10(String[] args) {
//        getLongestPalindrome("ababc");
//    }
//
//    public static void main9(String[] args) {
//        Scanner in = new Scanner(System.in);
//        int n = in.nextInt();
//        StringBuilder str = new StringBuilder();
//        int m = 0;
//        while(n != 0){
//            m++;
//            str.append(n%10);
//            if(m % 3 ==0){
//                str.append(',');
//            }
//            n/=10;
//        }
//        System.out.println(str.reverse().toString());
//    }
//    public static void main8(String[] args) {
//        int[] arr = {1,2,3,4,100,200};
//        int ret = MLS(arr);
//        System.out.println(Arrays.toString(arr));
//
//     }
//
//    public static int MLS (int[] arr) {
//        Arrays.sort(arr);
//        int len = arr.length - 1;
//        if(len == 1){
//            return arr[0];
//        }
//        int min = 1;
//        int sum = 1;
//        for(int i = 1; i <= len; i++){
//            if(arr[i] - arr[i - 1] == 1){
//                sum++;
//            }
//            if(sum > min){
//                min = sum;
//                sum = 1;
//            }
//        }
//        if(sum > min){
//            min = sum;
//        }
//        return min;
//    }
//
//    public static void main7(String[] args) {
//        Scanner in = new Scanner(System.in);
//        int x = in.nextInt();
//        int y = in.nextInt();
//        if(x % y == 0){
//            System.out.println(x);
//            return;
//        }
//        if(y % x == 0){
//            System.out.println(y);
//            return;
//        }
//        int z = 0;
//        int min = Math.min(x,y);
//        int x1 = x;
//        int y1 = y;
//        if(x < y){
//            z = x;
//            x = y;
//            y = z;
//        }
//        while(x1 != 0 || y1 != 0){
//            if(x1 < y1){
//                z = x1;
//                x1 = y1;
//                y1 = z;
//            }
//            z = x1 % y1;
//            x1 = y1;
//            y1 = z;
//        }
//        if(x1 == 1 || y1 == 1){
//            System.out.println(x * y);
//        }else{
//            System.out.println(min*y);
//        }
//    }
//    public static String countAndSay(int n) {
//        if(n == 1){
//            return "1";
//        }
//        StringBuilder str1 = new StringBuilder("1");
//        StringBuilder str2 = null;
//        for(int i = 2; i <= n; i++){
//            str2 = new StringBuilder();
//            int left = 0;
//            int right = 0;
//            int len = str1.length();
//            while(right < len){
//                if(str1.charAt(right) != str1.charAt(left)){
//                    str2.append(right - left);
//                    str2.append(str1.charAt(left));
//                    left = right;
//                }
//                right++;
//            }
//            str2.append(right - left);
//            str2.append(str1.charAt(left));
//            str1 = str2;
//        }
//        return str1.toString();
//    }
//
//
//    class ListNode {
//      int value;
//      ListNode next = null;
//      public ListNode(int value) {
//        this.value = value;
//      }
//    }
//
//
//    public ListNode addInList (ListNode head1, ListNode head2) {
//        if(head1 == null){
//            return head2;
//        }
//        if(head2 == null){
//            return head1;
//        }
//        StringBuilder str1 = new StringBuilder();
//        StringBuilder str2 = new StringBuilder();
//        while(head1 != null){
//            str1.append(head1.value);
//            head1 = head1.next;
//        }
//        while(head2 != null){
//            str2.append(head2.value);
//            head2 = head2.next;
//        }
//        long sum = Integer.parseInt(str1.toString()) + Integer.parseInt(str2.toString());
//        ListNode head = null;
//        ListNode cur = null;
//        int n = 0;
//        while(sum != 0){
//            cur = head;
//            n =(int) (sum % 10);
//            head = new ListNode(n);
//            head.next = cur;
//            sum /= 10;
//        }
//        return head;
//
//    }
//
//    public static void main6(String[] args) {
//        Scanner in = new Scanner(System.in);
//        int n = in.nextInt();
//        int x = in.nextInt();
//        //String f = in.nextLine();
//        int[] arr = new int[n];
//        for(int i = 0; i < n; i++){
//            arr[i] = in.nextInt();
//        }
//        int left = 0;
//        int right = 0;
//        int min = Integer.MAX_VALUE;
//        int sum = 0;
//        int[] arr1 = new int[2];
//        while(right < n){
//            if(sum < x){
//                sum += arr[right];
//                right++;
//            }else{
//                if(right - left < min){
//                    arr1[0] = left;
//                    arr1[1] = right - 1;
//                }
//                sum -= arr[left];
//                left++;
//            }
//        }
//        for(int i =0; i < 2; i++){
//            System.out.print(arr1[i]);
//            if(i < 1){
//                System.out.print(" ");
//            }
//        }
//    }
//    public static void main5(String[] args) {
//        Scanner in = new Scanner(System.in);
//        String str = in.nextLine();
//        String[] strs = str.split(" ");
//        StringBuilder stringBuilder = new StringBuilder();
//        for(int i = 0; i < strs.length; i++){
//            String str1 = strs[0];
//            if(str1 == null || str1.length() == 0){
//                continue;
//            }
//            char ch = str1.charAt(i);
//            if((ch >= 'A' && ch <= 'Z') || (ch <= 'z' && ch >= 'a')){
//                stringBuilder.append(Character.toUpperCase(ch));
//            }
//        }
//        System.out.println(stringBuilder.toString());
//    }
//
//    public static void main4(String[] args) {
//        Scanner in = new Scanner(System.in);
//        int n = in.nextInt();
//        String empty = in.nextLine();//
//        String str = in.nextLine();
//        if(str == null){
//            System.out.println(-1);
//        }
//        String[] s = str.split(" ");//
//        if(s.length <= 1){
//            System.out.println(-1);
//            return;
//        }
//        String str1 = s[0];
//        String str2 = s[1];
//        int x = -1;
//        int y = -1;
//        int min = Integer.MAX_VALUE;
//        String[] strs = new String[n];
//        for(int i = 0; i < n; i++){
//            strs[i] = in.nextLine();
//        }
//        for(int i = 0; i < n; i++){
//            if(str1.equals(strs[i])){
//                x = i;
//                for(int j = 0; j < n; j++){
//                    if(str2.equals(strs[j])){
//                        y = j;
//                        if(x > y){
//                            min = Math.min(min, x - y);
//                        }else{
//                            min = Math.min(min, y - x);
//                        }
//                    }
//                }
//            }
//        }
//        if(x == -1 || y == -1){
//            min = -1;
//        }
//        System.out.println(min);
//    }
//
//    public static void main3(String[] args) {
//        Scanner in = new Scanner(System.in);
//        // 注意 hasNext 和 hasNextLine 的区别
//        int len = in.nextInt();
//        int[] arr = new int[len];
//        for(int i = 0; i < len; i++){
//            arr[i] = in.nextInt();
//        }
//        int[] dp = new int[len + 1];
//        dp[0] = arr[0];
//        dp[1] = arr[1];
//        for(int i = 2; i < dp.length; i++){
//            dp[i] = Math.min(dp[i - 1], dp[i - 2]) + arr[i - 1];
//        }
//        System.out.println(dp[len]);
//
//        String s = "vsd0";
//    }
//
//    public static void main2(String[] args) {
//        Scanner in = new Scanner(System.in);
//        float f = in.nextFloat();
//        String ch = in.nextLine();
//        if(f <= 1.0){
//            if(ch.equals("y")){
//                System.out.println(25);
//                return;
//            }else{
//                System.out.println(20);
//                return;
//            }
//        }
//        int amount = 20;
//        f = f - 1;
//        while(f >= 1){
//            amount += 1;
//            f = f - 1;
//        }
//        if(f > 0){
//            amount += 1;
//        }
//        if(ch.equals("y")){
//            System.out.println(amount + 5);
//            return;
//        }else{
//            System.out.println(amount);
//        }
//    }
//
//    public static void main1(String[] args) {
//        Scanner in = new Scanner(System.in);
//        // 注意 hasNext 和 hasNextLine 的区别
//        String str = in.nextLine();
//        if(str.length() == 1){
//            System.out.println(str);
//            return;
//        }
//        char[] chars = new char[str.length()];
//        for(int i = 0; i < str.length(); i++){
//            chars[i] = str.charAt(i);
//        }
//
//        modify(chars, chars.length);
//        StringBuffer stringBuffer = new StringBuffer();
//        for(int i = 0; i < chars.length; i++){
//            if(chars[i] != 'A'){
//                stringBuffer.append(chars[i]);
//            }
//        }
//        if(stringBuffer.length() == 0){
//            System.out.println(0);
//        }else{
//            System.out.println(stringBuffer.toString());
//        }
//    }
//    private static void modify (char[] chars, int len){
//        int x = 0, y = 1;
//        int n = 0;
//        for(x = 0; x < len - 1;){
//            if(chars[x] == 'A'){
//                continue;
//            }
//            for(y = x + 1; y < len; y++){
//                if(chars[y] == 'A'){
//                    continue;
//                }
//                break;
//            }
//            if(y == len){
//                break;
//            }
//            if(chars[x] == chars[y]){
//                chars[x] = 'A';
//                chars[y] = 'A';
//                x = y + 1;
//                n = 1;
//            }else{
//                x = y;
//            }
//        }
//        if(n == 0){
//            return;
//        }
//        modify(chars, len);
//    }
}